package Leetcode.网格图;

import java.util.Arrays;

/**
 * @Author: kirito
 * @Date: 2024/5/6 11:36
 * @Description:
 *  摘樱桃
 * 困难
 * 相关标签
 * 相关企业
 * 给你一个 n x n 的网格 grid ，代表一块樱桃地，每个格子由以下三种数字的一种来表示：
 *
 * 0 表示这个格子是空的，所以你可以穿过它。
 * 1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
 * -1 表示这个格子里有荆棘，挡着你的路。
 * 请你统计并返回：在遵守下列规则的情况下，能摘到的最多樱桃数：
 *
 * 从位置 (0, 0) 出发，最后到达 (n - 1, n - 1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为 0 或者 1 的格子）；
 * 当到达 (n - 1, n - 1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
 * 当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为 0 ）；
 * 如果在 (0, 0) 和 (n - 1, n - 1) 之间不存在一条可经过的路径，则无法摘到任何一个樱桃。
 *
 *
 * 示例 1：
 *
 *
 * 输入：grid = [[0,1,-1],[1,0,-1],[1,1,1]]
 * 输出：5
 * 解释：玩家从 (0, 0) 出发：向下、向下、向右、向右移动至 (2, 2) 。
 * 在这一次行程中捡到 4 个樱桃，矩阵变成 [[0,1,-1],[0,0,-1],[0,0,0]] 。
 * 然后，玩家向左、向上、向上、向左返回起点，再捡到 1 个樱桃。
 * 总共捡到 5 个樱桃，这是最大可能值。
 * 示例 2：
 *
 * 输入：grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
 * 输出：0
 *
 *
 * 提示：
 *
 * n == grid.length
 * n == grid[i].length
 * 1 <= n <= 50
 * grid[i][j] 为 -1、0 或 1
 * grid[0][0] != -1
 * grid[n - 1][n - 1] != -1
 */

public class cherryPickup {
    public static void main(String[] args) {
        int[][] grid = {{0, 1, -1},
                        {1, 0, -1},
                        {1, 1, 1}};
        System.out.println(new cherryPickup().cherryPickup(grid));

    }

    public int cherryPickup2(int[][] grid) {
        // 定义二维数组f，用于存储到达每个位置的最大樱桃数量
        int n = grid.length;
        int[][] f = new int[n][n];
        // 将f数组初始化为最小整数值，表示无法到达的位置
        for (int i = 0; i < n; ++i) {
            Arrays.fill(f[i], Integer.MIN_VALUE);
        }
        // 起点位置的樱桃数量
        f[0][0] = grid[0][0];
        // 遍历从(0,0)到(n-1,n-1)的所有位置
        for (int k = 1; k < n * 2 - 1; ++k) {
            // 遍历x1和x2的位置，x1 <= x2
            for (int x1 = Math.min(k, n - 1); x1 >= Math.max(k - n + 1, 0); --x1) {
                for (int x2 = Math.min(k, n - 1); x2 >= x1; --x2) {
                    // 计算对应的y1和y2位置
                    int y1 = k - x1, y2 = k - x2;
                    // 如果某个位置有障碍物，则该位置的最大樱桃数量设为最小整数值
                    if (grid[x1][y1] == -1 || grid[x2][y2] == -1) {
                        f[x1][x2] = Integer.MIN_VALUE;
                        continue;
                    }
                    // 初始化当前位置的最大樱桃数量
                    int res = f[x1][x2];
                    // 如果x1 > 0，表示可以往左走，则尝试更新当前位置的最大樱桃数量
                    if (x1 > 0) {
                        res = Math.max(res, f[x1 - 1][x2]);
                    }
                    // 如果x2 > 0，表示可以往下走，则尝试更新当前位置的最大樱桃数量
                    if (x2 > 0) {
                        res = Math.max(res, f[x1][x2 - 1]);
                    }
                    // 如果x1 > 0且x2 > 0，表示可以左右走，则尝试更新当前位置的最大樱桃数量
                    if (x1 > 0 && x2 > 0) {
                        res = Math.max(res, f[x1 - 1][x2 - 1]);
                    }
                    // 加上当前位置的樱桃数量
                    res += grid[x1][y1];
                    // 如果x2 != x1，表示不是同一个位置，则再加上x2位置的樱桃数量
                    if (x2 != x1) {
                        res += grid[x2][y2];
                    }
                    // 更新当前位置的最大樱桃数量
                    f[x1][x2] = res;
                }
            }
        }
        // 返回终点位置的最大樱桃数量，如果无法到达则为0
        return Math.max(f[n - 1][n - 1], 0);
    }

    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        int[][][] memo = new int[n * 2 - 1][n][n];
        for (int[][] m : memo) {
            for (int[] r : m) {
                Arrays.fill(r, -1); // -1 表示没有计算过
            }
        }
        return Math.max(dfs(n * 2 - 2, n - 1, n - 1, grid, memo), 0);
    }

    private int dfs(int t, int j, int k, int[][] grid, int[][][] memo) {
        // 不能出界，不能访问 -1 格子
        if (j < 0 || k < 0 || t < j || t < k || grid[t - j][j] < 0 || grid[t - k][k] < 0) {
            return Integer.MIN_VALUE;
        }
        if (t == 0) { // 此时 j = k = 0
            return grid[0][0];
        }
        if (memo[t][j][k] != -1) { // 之前计算过
            return memo[t][j][k];
        }
        int res = Math.max(
                Math.max(dfs(t - 1, j, k, grid, memo), dfs(t - 1, j, k - 1, grid, memo)),
                Math.max(dfs(t - 1, j - 1, k, grid, memo), dfs(t - 1, j - 1, k - 1, grid, memo)))
                + grid[t - j][j] + (k != j ? grid[t - k][k] : 0);
        memo[t][j][k] = res; // 记忆化
        return res;
    }
}
